#!/usr/bin/env python3
# -*- encoding: utf-8 -*-
"""
@UserFor     :   ***    ***
@File        :   middle-198-打家劫舍.py
@Email       :   18574945291@163.com
@Modify Time :   2021-02-15 15:09
@Author      :   code_wizard (wll) 
"""

# 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
# 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# dp[i] = max(dp[i-1],nums[i-1] + dp[i-2])。

class Solution:
    """
        定义一个数组 dp，dp[i] 表示抢劫到第 i 个房子时，可以抢劫的最大数量。我们考虑 dp[i]，
    此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时累计的金额即为
    dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2]，因为我们不
    能够抢劫第 i-1 个房子，否则会触发警报机关。因此本题的状态转移方程为 dp[i] = max(dp[i-1],
    nums[i-1] + dp[i-2])。
    """
    def rob(self, nums):
        if len(nums)< 1:
            return -1
        if len(nums) == 1:
            return nums[0]
        dp = [0 for i in nums]
        n = len(nums)
        dp[0] = nums[0]
        for i,j in enumerate(nums):
            print(dp)
            if i < 1:
                dp[i] = max(dp[i],j)
            else:
                dp[i] = max(dp[i-1],j+dp[i-2])
        return dp[n-1]


    # 这里有大佬的更帅的版本  dp空间优化
    def rob_plus(self, nums) -> int:
        prev = 0
        curr = 0
        for i in nums:
            prev, curr = curr, max(curr, prev + i)
        return curr

if __name__ == '__main__':
    obj= Solution()
    # lis = [1,2,3,1]
    lis = [2,7,9,3,1]
    print(obj.rob(lis))